package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 最长递增子序列
 * @date 2025/5/29 10:20
 */
public class LengthOfLIS_300 {

    public static void main(String[] args) {
        LengthOfLIS_300 lengthOfLIS300 = new LengthOfLIS_300();

        int[] nums = {0, 1, 0, 3, 2, 3};
//        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
//        int[] nums = {7, 7, 7, 7, 7, 7, 7};
//        int[] nums = {4, 10, 4, 3, 8, 9};
        System.out.println(lengthOfLIS300.lengthOfLIS3(nums));
    }

    /**
     * 个解：dp-参照dmsxl
     */
    public int lengthOfLIS4(int[] nums) {
        if (nums.length == 0) return 0;

        // 1.dp[i]
        // 以 i 为结尾的，最长 严格递增 子序列的长度
        int[] dp = new int[nums.length];
        // 2.递推公式
        // 对于所有dp[i]，都要在j∈[i-1, 0]区间从后往前遍历，找到最大的dp[j]Max，更新dp[i] = dp[j]Max + 1。

        // 3.初始化
        dp[0] = 1;

        // 4.遍历
        // 两层遍历；
        // 第一层，从前往后，因为dp[i]，依赖于前面。
        // 第二层，从后往前，因为dp[i]要在前面所有dp[]中，满足条件的最大值基础上进行 + 1。
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                // 这样dp[i]会无限增大
//                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j]) + 1;
                // 而这样才是正确逻辑，dp[i]与每个dp[j]+1比较，取较大的一个。因为dp[j]+1表示，在nums[i]>nums[j]前提下，在以j结尾的最大严格递增子序列中，再加上一位元素，即nums[i]。
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            maxLength = Math.max(dp[i], maxLength);
        }

        return maxLength;
    }

    /**
     * 个人解法：dp（错误！！！）
     * <p>
     * 错误原因：递推公式有问题，在nums[i]>nums[i-1]时，也要从后往前遍历，再找一遍，否则可能漏计算前面更小的元素；因为题目并不要求子序列 连续！！！
     * 如，[0,1,0,3]；
     * <p>
     * 错误示例：其dp[0]=1，dp[1]=2，dp[2]=1，根据上述递推公式，因为nums[3]=3 > nums[2]=0，所以，dp[3]=dp[2]+1=1+1=2。
     * 但实际上，对于i=3来说，其最长严格递增子序列是{0,1,3}，应该从i=0开始，而不是从i=2开始。
     * <p>
     * 正确递推公式：对于所有 i，都应该j∈[i-1, 0]区间从后往前遍历，然后找到最大的dp[j]Max，更新dp[i] = dp[j]Max + 1。
     */
    public int lengthOfLIS3(int[] nums) {
        if (nums.length == 0) return 0;

        // 1.dp[i]
        int[] dp = new int[nums.length];
        // 2.递推公式
        // 1）若nums[i]>nums[i-1]，则dp[i]=dp[i-1]+1；
        // 2）反之，j∈[i-1, 0]区间从后往前遍历，找到第一个nums[i]>nums[j]，dp[i]=dp[j]+1

        // 3.初始化
        dp[0] = 1;

        // 4.遍历
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[i] > nums[j]) dp[i] = dp[j] + 1;
                }
            }
            maxLength = Math.max(dp[i], maxLength);
        }

        return maxLength;
    }

    /**
     * dmsxl：dp-两层for循环
     * <p>
     * T(n) = O(n^2)；其中 n 为数组 nums 的长度。动态规划的状态数为 n，计算状态 dp[i] 时，需要 O(n) 的时间遍历 dp[0…i−1] 的所有状态，所以总时间复杂度为 O(n^2）。
     * S(n) = O(n)；需要额外使用长度为 n 的 dp 数组。
     */
    public int lengthOfLIS2(int[] nums) {
        // 1.dp[i]含义
        // 以下标 i 结尾的子序列中，拥有的最长严格递增子序列的长度
        int[] dp = new int[nums.length];
        // 2.递推公式

        // 3.初始化
        // 因为dp[1]能被dp[0]推导出来，就不用初始化dp[1]
        // 若nums[1]>nums[0]，则dp[1]=dp[0]+1=2；否则dp[1]=dp[0]=1;
        dp[0] = 1;

        // 4.遍历顺序
        // i依赖于前面项的结果，所以从前往后；若从后往前，i就找不到依赖项
        int maxLength = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            // 从后往前，
            // 因为不是找连续递增，所以，dp[i]前面的每个dp数组都要判断（从i-1遍历到0），每次取最大值更新为最新的dp[i]
            // j=i不用判断，直接从i-1开始
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }

    /**
     * 个解：错误解法；
     * <p>
     * 错误原因：递推公式考虑错误;
     * 1. 本题只找最长递增子序列，而不是连续最长递增（leetcode674最长连续递增序列）；
     * 2. 若dp[i]只与dp[i-1]比较，就是在找连续最长递增；
     * 3. 所以，dp[i]应该与前面每一个dp[j]比较（0 <= j <= i），若dp[i]>dp[j]，表明以j结尾的最长递增子序列中，可以加上i，所以dp[i]=dp[j]+1。
     * 4. 又因为要与前面每个dp[j]比较，所以要遍历，取dp[j]+1的最大值。
     */
    public int lengthOfLIS(int[] nums) {
        // 1.dp[i]含义
        // 以下标 i 结尾的子序列中，拥有的最长严格递增子序列的长度
        int[] dp = new int[nums.length];
        // 2.递推公式
        // 若nums[i]>nums[i-1]，那么dp[i]=dp[i-1]+1；否则dp[i]=dp[i-1]

        // 错误！！！
        // 这样是在考虑连续递增（也不完全正确，因为连续递增每个dp[i]初始应该为1，要依赖dp[i-1]）

        // 3.初始化
        // 因为dp[1]能被dp[0]推导出来，就不用初始化dp[1]
        // 若nums[1]>nums[0]，则dp[1]=dp[0]+1=2；否则dp[1]=dp[0]=1;
        dp[0] = 1;

        // 4.遍历顺序
        // 从前往后
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                // 5.日志
                dp[i] = dp[i - 1] + 1;
                System.out.println("dp[" + i + "]=" + dp[i] + " = dp[" + (i - 1) + "]+1=" + (dp[i - 1] + 1));
            } else {
                dp[i] = dp[i - 1];
                System.out.println("dp[" + i + "]=" + dp[i] + " = dp[" + (i - 1) + "]=" + dp[i - 1]);
            }
        }

        return dp[nums.length - 1];
    }

}
